package com.yusong.algorithm;


import com.yusong.algorithm.data.DataConstants;

/**
 * 归并排序
 */
public class MergeSort extends AbstractSort {

    @Override
    public void sort(Comparable[] a) {
        //sortTop(a, 0, a.length - 1);
        sortDown(a, 1);

    }

    /**
     * 从顶往下：化整为零
     * 安排多次merge的正确顺序
     * @param a
     * @param low
     * @param high
     */
    public void sortTop(Comparable[] a, int low, int high) {
        if (high <= low) {
            return;
        }
        int middle = Math.round((low + high) / 2);
        sortTop(a, low, middle);
        sortTop(a, middle + 1, high);
        merge(a, low, middle, high);
    }


    /**
     * 从底往上 ：循序渐渐
     *  安排多次merge的正确顺序
     * 数组长度为2的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同。
     */
    public void sortDown(Comparable[] a, int size) {
        int length = a.length;
        if (size >= length) {
            return;
        }
        int index = 0;
        while (index < length) {
            int high = Math.min(index + 2 * size - 1, length - 1);
            merge(a, index, index + size - 1, high);
            index += size*2;
        }
        sortDown(a,size*2);
    }


    /**
     * 合并两个数组
     */
    private void merge(Comparable[] a, int low, int middle, int high) {
        int i = low;
        int j = middle + 1;
        Comparable[] aux = copy(a, null);
        int index = low;
        while (index <= high) {
            if (i > middle) {
                while (j <= high) {
                    a[index++] = aux[j++];
                }
                return;
            }
            if (j > high) {
                while (i <= middle) {
                    a[index++] = aux[i++];
                }
                return;
            }
            if (less(aux[i], aux[j])) {
                a[index++] = aux[i++];
            } else {
                a[index++] = aux[j++];
            }
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(DataConstants.NUM_SIMPLE);
        show(DataConstants.NUM_SIMPLE);
    }


}

/**
 * 可以看到，希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。在继续学习之前，请在你的计算机上用
 * 时间复杂度：NlogN
 * 可以用归并排序处理数百万甚至更大规模的数组，这是插入排序或者选择排序做不到的。
 * 归并排序的主要缺点是辅助数组所使用的额外空间和N的大小成正比。另一方面，通过一些细致的思考我们还能够大幅度缩短归并排序的运行时间。
 */
